package LeetCode.prefixSum;

import java.util.HashMap;
import java.util.Map;

/**
 * @author : LdLtd
 * @Date : 2023/8/2
 * @Description:560. 和为 K 的子数组
 */
public class subarray_sum_equals_k {
    public static void main(String[] args) {

    }
    class Solution {
        /*利用hash表优化，计算前缀和
        * j--i的和为K可以表示为pre[i]-pre[j-1]
        * 将当前的和存入map中，如果存在【当前值-k】的map
        * 则结果加上map的值
        * */
        public int subarraySum(int[] nums, int k) {
            int res=0,pre=0;
            Map<Integer,Integer> map=new HashMap<>();
            map.put(0,1);
            for (int num : nums) {
                pre+=num;
                if(map.containsKey(pre-k)){
                    res+=map.get(pre-k);
                }
                map.put(pre,map.getOrDefault(pre,0)+1);
            }
            return res;
        }
    }
}
